insertion sort 是一個 internal sort

其worst case 的時間複雜度為 O(n^2)

如果要由小排到大

核心概念為逐次檢查元素與其之前元素的大小

如果比之前的元素小則將前面的元素往後推

直到找到正確的位置為止

因為在 scan 的過程中會發生多次的搬移

所以如果以 linked list 來實作的話會快很多

Array版 – Java